package 平衡二叉树110;


/**
 * @author 谢阳
 * @version 1.8.0_131
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        //if (root == null) {
        //    return true;
        //}
        //return Math.abs(dfs(root.left) - dfs(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        return dfs(root) >= 0;
    }

    private int dfs(TreeNode node) {
        //if (node == null) {
        //    return 0;
        //}
        //return Math.max(dfs(node.right),dfs(node.left)) + 1;
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == -1 || right == -1 || (Math.abs(left - right) > 1)) {
            return -1;
        }
        return Math.max(dfs(node.right),dfs(node.left)) + 1;
    }
}


class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
